// Problem:    186
// Title:      Connectedness of a network
// Date:       15-Mar-2008
// Difficulty: 1
// Fun Rating: 1
// Time:       N
// Space:      N
// Closed:     Y
// Answer:     2325629

#define VERBOSE    0
#define USE_FOREST 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

class lagged_fibonacci_generator
{
	std::vector<int> S;
	int i;
	int M;

public:
	lagged_fibonacci_generator(int modulus) : S(55), i(0), M(modulus)
	{
		for (int k = 1; k <= 55; k++)
		{
			S[k-1] = ((long long)k*k*k*300007 - 200003*k + 100003) % M;
		}
	}

	int next()
	{
		if (i < 55)
			return S[i++];

		int x = S[i%55] = (S[i%55]+S[(i-24)%55])%M;
		i++;
		return x;
	}
};

#if !USE_FOREST
class social_network
{
	struct friend_info
	{
		int next;	// next friend in the chain, or -1 if last
		int head;	// if >=0, the head; if <0, this node is the head and this member is the count
	public:
		friend_info() : next(-1), head(-1) { }
	};
	std::vector<friend_info> _stat;

public:
	social_network(int users) : _stat(users) { }

	bool connected(int x, int y) const
	{
		int x0 = (_stat[x].head >= 0)? _stat[x].head : x;
		int y0 = (_stat[y].head >= 0)? _stat[y].head : y;
		return x0 == y0;
	}

	// Gets the number of users that are connected to this user.
	int connections(int x) const
	{
		int x0 = (_stat[x].head >= 0)? _stat[x].head : x;
		return -_stat[x0].head;
	}

	bool connect(int x, int y)
	{
		int x0 = (_stat[x].head >= 0)? _stat[x].head : x;
		int y0 = (_stat[y].head >= 0)? _stat[y].head : y;
		if (x0 == y0)
			return false;

		// Make sure the chain of x is longer than the chain of y.
		if (-_stat[x0].head < -_stat[y0].head)
		{
			std::swap(x, y);
			std::swap(x0, y0);
		}

		// Merge friend chain y0 into friend chain x0.
		_stat[x0].head += _stat[y0].head;
		int last = y0;
		for (int i = y0; i >= 0; i = _stat[i].next)
		{
			_stat[i].head = x0;
			last = i;
		}
		_stat[last].next = _stat[x0].next;
		_stat[x0].next = y0;
		return true;
	}
};
#else
class social_network
{
	class node_info
	{
		// If _parent >= 0, it points to the parent.
		// If _parent < 0, then -parent = flag, where
		// (flag >> 24) is the rank of the node;
		// (flag & 0xffffff) is the size of the group
		int _parent;
	public:
		node_info() : _parent(-1) { }

		int parent() const { return _parent; }
		bool is_root() const { return _parent < 0; }
		int rank() const { return (-_parent) >> 24; }
		int size() const { return (-_parent) & 0xffffff; }

		int set_parent(int x) { return _parent = x; }
		void increment_rank() { _parent -= 0x1000000; }
		void increment_size(int n) { _parent -= n; }
	};
	std::vector<node_info> _nodes;

public:
	social_network(int users) : _nodes(users) 
	{
		assert(users >= 0);
		assert(users <= 0xffffff);
	}

	int find(int x)
	{
		if (_nodes[x].is_root())
			return x;
		else if (_nodes[_nodes[x].parent()].is_root())
			return _nodes[x].parent();
		else
			return _nodes[x].set_parent(find(_nodes[x].parent()));
	}

	int group_size(int x)
	{
		int x0 = find(x);
		return _nodes[x0].size();
	}

	bool merge(int x, int y)
	{
		int x0 = find(x);
		int y0 = find(y);
		if (x0 == y0)
			return false;

		// Merge the tree with lower rank/size into the tree with higher rank/size.
		// Always merge y0 into x0.
		if (-_nodes[x0].parent() < -_nodes[y0].parent())
			std::swap(x0, y0);

		if (_nodes[x0].rank() == _nodes[y0].rank())
		{
			_nodes[x0].increment_rank();
		}
		_nodes[x0].increment_size(_nodes[y0].size());
		_nodes[y0].set_parent(x0);
		return true;
	}

	// Gets the number of users that are connected to this user.
	int connections(int x) { return group_size(x); }
	bool connect(int x, int y) { return merge(x, y); }
};
#endif

void solve_problem_186()
{
#if 0
	const int N = 100;
#else
	const int N = 1000000;
#endif

	lagged_fibonacci_generator S(N);
	social_network network(N); // , network2(N);
	const int PM = 524287 % N;

#if VERBOSE
		std::cout << "PM is " << PM << std::endl;
#endif

	int calls = 0;
	while (1)
	{
		// Generate next call.
		int x = S.next();
		int y = S.next();
#if VERBOSE >= 2
		std::cout << x << ", " << y << std::endl;
#endif
		if (x == y)
			continue;
		++calls;
		if (calls == 8)
		{
			int kk = 1;
		}
		if (network.connect(x, y))
		{
			// Check if we've got enough friends of PM?
			int count = network.connections(PM);
#if VERBOSE
			std::cout << "After " << calls << " calls, PM has " << count << " friends." << std::endl;
#endif
			if (count*100 >= N*99)
				break;
		}
	}
	std::cout << calls << std::endl;
}
